/**
 * 交换数组中指定的位置
 * @param arr
 * @param i1
 * @param i2
 */
function swap(arr, i1,i2) {
    var temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
}
/**
 * 选择排序
 * @param arr
 */
function selectSort(arr){
    for(var i = 0; i < arr.length - 1;i ++){
        var min = arr[i];
        var index = i;
        for(var j = i + 1;j < arr.length;j ++){
            if(min > arr[j]){
                min = arr[j];
                index = j;
            }
        }
        swap(arr,i , index);
    }
}

/**
 * 冒泡排序
 * @param arr
 */
function bubbleSort(arr){
    for(var i = 0 ;i < arr.length - 1;i ++){
        for(var j = 0;j < arr.length - 1 - i;j ++){
            if(arr[j] > arr[j + 1] ){
                swap(arr,j,j + 1);
            }
        }
    }
}

/**
 * 插入排序
 * @param arr
 */
function insertSort(arr) {
    for(var i = 1;i < arr.length; i ++){
        if(arr[i] < arr[i - 1]){
            //将第i位的值加入到前面有序队列的正确位置
             var temp = arr[i];
             for(var j = i;j >= 0;j --){
                 if(j > 0 && arr[j-1] > temp){
                     arr[j] = arr[j - 1];
                 }
                 else{
                     arr[j] = temp;
                     break;
                 }
             }
        }
    }
}
/**
 * 快速排序
 * @param arr
 */
function quickSort(arr){
    function _quickSort(arr,start,end) {
        if (start >= end || start > arr.length - 1) return;
        var low = start;
        var high = end;
        var key = arr[end];
        while(low < high){
            while(low < high && arr[low] <= key) low++;
            arr[high] = arr[low];
            while(low < high && arr[high] >= key) high--;
            arr[low] = arr[high];
        }
        arr[low] = key;
        _quickSort(arr, start, low - 1);
        _quickSort(arr, low + 1, end);
    }
    _quickSort(arr,0,arr.length - 1);
}


var arr = [5,1,3,4,7,6];
// selectSort(arr);
// quickSort(arr);
// bubbleSort(arr);
insertSort(arr);
console.log(arr);